package com.linyaonan.leetcode.medium._48;

/**
 * 给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
 * <p>
 * 你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
 * <p>
 * 输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
 * 输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
 *  
 * <p>
 * 提示：
 * <p>
 * n == matrix.length == matrix[i].length
 * 1 <= n <= 20
 * -1000 <= matrix[i][j] <= 1000
 * <p>
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/rotate-image
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class RotateImage {

    /**
     * [5,1,9,11]                       [15,13,2,5]
     * [2,4,8,10]         =>            [14,3,4,1]
     * [13,3,6,7]                       [12,6,8,9]
     * [15,14,12,16]                    [16,7,10,11]
     * <p>
     * 以index=0,1 为例 会进行位置交换 => 1.max, max.max-1,max-1.0
     * <p>
     * 推导出index=m,n 为例 会进行位置交换 => n.max-m => max-m.max-n => max-n,m
     * <p>
     * 通过上面的推到可以得出数值的转换规律，再借助一个是否已经移动的辅助矩阵进行判断即可
     *
     * @param matrix
     */
    public void rotate(int[][] matrix) {
        // 1. 异常边界
        if (matrix.length == 0 || matrix.length == 1) {
            return;
        }
        // 2. 创建一个辅助矩阵
        int[][] temp = new int[matrix.length][matrix.length];
        // 得到上面的max
        int max = matrix.length - 1;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                // 表示并未移动过
                if (temp[i][j] != 1) {
                    // 3. 首先记录到目前的数值
                    int tempValue = matrix[i][j];
                    swap(matrix, max - j, i, i, j);
                    swap(matrix, max - i, max - j, max - j, i);
                    swap(matrix, j, max - i, max - i, max - j);
                    matrix[j][max - i] = tempValue;
                    temp[i][j]=1;
                    temp[max - j][i] = 1;
                    temp[max - i][max - j] = 1;
                    temp[j][max - i] = 1;
                }
            }
        }
    }

    private void swap(int[][] matrix, int x, int y, int x1, int y1) {
        int temp = matrix[x][y];
        matrix[x][y] = matrix[x1][y1];
        matrix[x1][y1] = temp;
    }
}